package Algorithm.Sort;

import java.util.Arrays;

/**
 * 希尔排序法又称缩小增量法。
 * 希尔排序法的基本思想是：
 * 先选定一个整数gap(gap一般为数组长度的一半或1/3)，
 * 把待排序数组以gap为间隔分成个组，个组之间内部使用插入排序，排序之后，再将gap/=2或gap/=3，
 * 重复上述流程，直到gap=1，此时数组已经近乎有序，利用插入排序对近乎有序的数组进行调整。
 */
public class ShellSort {
    // 插入排序
    public static void insertSort(int[] arr) {
        // 有序区间（已排序区间）[0,i]
        for (int i = 1; i < arr.length; i++) {
            // 待排序区间[i...n]
            // 待排序区间的第一个元素arr[i]
            // 从待排序区间的第一个元素向前看，找到合适的位置插入
            for (int j = i; j > 0; j--) { // 表示取无序区间的第一个元素与有序区间进行比较
                // 循环已排区间
                // arr[j - 1]已排序区间的最后一个元素
                // 相等也不交换，保证稳定性
                // 此时说明arr[j] > 已排区间的最大值，a[j]已经有序了---直接下次循环
                if (arr[j] >= arr[j - 1]) {
                    break;
                } else { // 冒泡排序（arr[j] < arr[j - 1]）
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 希尔排序
    // ap,gap一般为数组长度的一半或1/3,将待排序的数组先按照
    //gap分组，不同组之间内部使用插入排序，排序之后，再将
    //gap/=2或gap/=3，重复上述流程，直到gap=1，此时数组已经
    //近乎有序，利用插入排序对近乎有序的数组进行调整。
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            // 当gap>1时，对arr以gap为间隔进行分组，组内进行插入排序
            insertionSortByGap(arr, gap);
            gap = gap >> 1;
        }
        // 此时gap==1,数组接近有序，对此时的arr进行插入排序
        insertSort(arr);
    }

    // 对arr以gap为间隔进行分组，组内进行插入排序
    public static void insertionSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j - gap >= 0; j = j - gap) {
                if (arr[j] > arr[j - gap]) {
                    break;
                }
                if (arr[j] < arr[j - gap]) {
                    swap(arr, j, j - gap);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr2 = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        shellSort(arr2);
        System.out.println(Arrays.toString(arr2));
    }
}
